/**
 * Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。
 *
 * 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。
 *
 * Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。
 *
 * 假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。
 * https://leetcode.cn/problems/stone-game/description/
 */
class StoneGame {
    /**
     * 法一：递归搜索，dfs(i,n-1)表示，在i,n-1中先手减去后手的分数
     */
    int[][] memo;
    public boolean stoneGameDp(int[] piles) {
        int n=piles.length;
        memo=new int[n][n];
        return stoneGame(0,n-1,piles)>0;
    }
    public int stoneGame(int i,int j,int[] piles) {
        if(i>j) {
            return 0;
        }
        if(memo[i][j]!=0) {
            return memo[i][j];
        }
        int left=piles[i]-stoneGame(i+1,j,piles);
        int right=piles[j]-stoneGame(i,j-1,piles);
       memo[i][j]=Math.max(left,right);
       return memo[i][j];
    }
    /**
     * 法二：动态规划
     * dp[i][j].fir = x 表示，对于 piles[i...j] 这部分石头堆，先手能获得的最高分数为 x。
     *
     * dp[i][j].sec = y 表示，对于 piles[i...j] 这部分石头堆，后手能获得的最高分数为 y。
     *
     * 举例理解一下，假设 piles = [2, 8, 3, 5]，索引从 0 开始，那么：
     *
     * dp[0][1].fir = 8 意味着：面对石头堆 [2, 8]，先手最多能够获得 8 分；dp[1][3].sec = 5 意味着：面对石头堆 [8, 3, 5]，后手最多能够获得 5 分。
     *
     * 我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n-1].fir - dp[0][n-1].sec，即面对整个 piles，先手的最优得分和后手的最优得分之差。
     * dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
     * dp[i][j].fir = max(     选择最左边的石头堆     ,     选择最右边的石头堆      )
     * # 解释：我作为先手，面对 piles[i...j] 时，有两种选择：
     * # 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j]
     * # 但是此时轮到对方，相当于我变成了后手；
     * # 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1]
     * # 但是此时轮到对方，相当于我变成了后手。
     *
     * if 先手选择左边:
     *     dp[i][j].sec = dp[i+1][j].fir
     * if 先手选择右边:
     *     dp[i][j].sec = dp[i][j-1].fir
     * # 解释：我作为后手，要等先手先选择，有两种情况：
     * # 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j]
     * # 此时轮到我，我变成了先手；
     * # 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1]
     * # 此时轮到我，我变成了先手。
     * 根据 dp 数组的定义，我们也可以找出 base case，也就是最简单的情况：
     * dp[i][j].fir = piles[i]
     * dp[i][j].sec = 0
     * 其中 0 <= i == j < n
     * # 解释：i 和 j 相等就是说面前只有一堆石头 piles[i]
     * # 那么显然先手的得分为 piles[i]
     * # 后手没有石头拿了，得分为 0
     * 这里需要注意一点，我们发现 base case 是斜着的，而且我们推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]
     *  判断 dp 数组遍历方向的原则，算法应该倒着遍历 dp 数组
     * @param nums
     * @return
     */
    public boolean stoneGame(int[] piles) {
        int n=piles.length;
        Pair[][] dp=new Pair[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                dp[i][j]=new Pair(0,0);
            }
        }
        for(int i=0;i<n;i++) {
            dp[i][i].fir=piles[i];
            dp[i][i].sec=0;
        }
        for(int i=n-2;i>=0;i--) {
            for(int j=i+1;j<n;j++) {
                int left=piles[i]+dp[i+1][j].sec;
                int right=piles[j]+dp[i][j-1].sec;
                if(left>right) {
                    dp[i][j].fir=left;
                    dp[i][j].sec=dp[i+1][j].fir;
                } else {
                    dp[i][j].fir=right;
                    dp[i][j].sec=dp[i][j-1].fir;
                }
            }
        }
        Pair res=dp[0][n-1];
        return res.fir-res.sec>0;
    }
}
class Pair{
    int fir;
    int sec;
    public Pair(int fir,int sec) {
        this.fir=fir;
        this.sec=sec;
    }
}